class Solution {  //前缀和O(n)
public:
    int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    vector<int> f(n), g(n);  //f为前缀和数组、g为后缀和数组
    //数组越界：f[0]=f[-1]+nums[-1]->f[0]=0、g[n-1]=g[n]+nums[n]->g[n-1]=0
    //1.预处理出前缀和数组和后缀和数组
    for(int i = 1; i < n; i++)  f[i] = f[i-1] + nums[i - 1];  //从前往后
    for(int i = n - 2; i >= 0; i--)  g[i] = g[i + 1] + nums[i + 1];  //从后往前

    //2.使用前缀和数组和后缀和数组
    for(int i = 0; i < n; i++)  if(f[i] == g[i])  return i;   
    return -1;
    }
};